1. Field of the Invention
The present invention generally relates to global routing determination methods and storage mediums, and more particularly to a global routing determination method for determining a global routing of a circuit, and to a computer-readable storage medium which stores a program for causing a computer to determine a global routing of a circuit according to such a global routing determination method.
When designing an integrated circuit such as an LSI circuit by CAD, it is possible to roughly categorize the design stage into a logic design and a physical design. The logic design determines how to realize the logic of the circuit which is to be designed. The physical design determines the arrangement (also referred to as layout or placement) of elements such as cells and gates, wirings and the like which form the circuit, based on the result of the logic design. When making the physical design, the layout of the wirings is basically determined by a global routing and a local (or detailed) routing. The global routing determines the general arrangement of the wirings together with the general arrangement of the elements and the like. On the other hand, the local routing determines the actual detailed arrangement of the wirings depending on the actual arrangement of the elements and the like.
The present invention relates to a global routing method used to make the global routing described above, and also relates to a computer-readable storage medium which stores a program for causing the computer to determine the global routing.
2. Description of the Related Art
Due to the progresses made in the circuit technology, the integration density of the integrated circuit has improved considerably and the circuit scale of the integrated circuit has increased notably in recent years. Conventionally when designing the circuit by CAD, the circuit delay taken into consideration was primarily the delays caused by gates which form the circuit. However, as the integration density of the integrated circuit improved, delays caused by the wirings have increased and are becoming no longer negligible in order to further improve the circuit performance. For this reason, there are demands to realize a method of designing the wirings by taking into consideration the delays caused by the wirings.
Conventionally, as a method of designing the wirings by taking into consideration the delays caused by the wirings, there was a method which determines the wirings so that each wiring length becomes a minimum. However, this conventional method did not accurately consider the delay of the actual wiring from one terminal to another terminal, as explained in the following.
First, a description will be given of the Elmore delay. It is assumed for the sake of convenience that a tree T has a source s0. If an edge from a node v towards the source s0 is denoted by ev, a resistance of the edge ev is denoted by rev, a capacitance of the edge ev is denoted by Cev, a subtree of the node v is denoted by Tv, a capacitance of the subtree Tv is denoted by Cv, an ON-resistance of an output driver of the source s0 is denoted by rd, and a sum total of the wiring lengths is denoted by Cs0, the Elmore delay from the source s0 to the target v can be described by the following formula (1).                               D          ⁢                      xe2x80x83                    ⁢                      (            v            )                          =                              rdC            s0                    +                                    ∑                              ev                ∈                                  path                  ⁢                                      xe2x80x83                                    ⁢                                      (                                          s0                      ,                      v                                        )                                                                        ⁢                          xe2x80x83                        ⁢                                          r                ev                            ⁢                              xe2x80x83                            ⁢                              (                                                                            C                      ev                                        /                    2                                    +                  Cv                                )                                                                        (        1        )            
In the formula (1), the first term indicates that the delay from the source s0 to the target v becomes shorter as the sum total Cs0 of the wiring lengths becomes shorter. In addition, in the formula (1), the second term indicates that the delay becomes shorter as the wiring length from the source s0 to the target v becomes shorter, and that the delay becomes shorter as the capacitance Cv of the subtree Tv connected to the target v becomes smaller.
Next, a description will be given of the mechanism by which the wiring delays become different even for the same wiring length. FIGS. 1A and 1B respectively are diagrams showing a case where a region including cells which form a circuit is successively divided into a plurality of blocks, and the global routing among the cells is hierarchically determined while arranging the cells in the blocks. In this particular case, the region is formed by 2xc3x972 blocks, and there exist 3 terminals which are to be connected by the wirings. In FIGS. 1A and 1B, a black circular mark indicates the terminal, and a straight line connecting the terminals indicates the wiring.
In FIGS. 1A and 1B, it is assumed for the sake of convenience that each block has a side with a resistance R, a terminal s0 has an ON-resistance rd, a terminal v1 has a capacitance C1, and a terminal v2 has a capacitance C2. The wiring delay caused by the wiring from the terminal s0 to the terminals v1 and v2 can be described as follows.
In the case shown in FIG. 1A, a wiring delay Da(v1) from the terminal s0 to the terminal v1 can be described by the following formula (2), and a wiring delay Da(v2) from the terminal s0 to the terminal v2 can be described by the following formula (3).
Da(v1)=rdxc3x97(C+C1+C2)+Rxc3x97(C/2+C1+C2)xe2x80x83xe2x80x83(2)
Da(v2)=rdxc3x97(C+C1+C2)+Rxc3x97(C/2+C1+C2)+Rxc3x97C2xe2x80x83xe2x80x83(3)
On the other hand, in the case shown in FIG. 1B, a wiring delay Db(v1) from the terminal s0 to the terminal v1 can be described by the following formula (4), and a wiring delay Db(v2) from the terminal s0 to the terminal v2 can be described by the following formula (5).
Db(v1)=rdxc3x97(3C/2+C1+C2)+Rxc3x97C1xe2x80x83xe2x80x83(4)
Db(v2)=rdxc3x97(3C/2+C1+C2)+2Rxc3x97C2xe2x80x83xe2x80x83(5)
As may be seen from a comparison of FIGS. 1A and 1B, the wiring length in the case shown in FIG. 1A is shorter than the wiring length in the case shown in FIG. 1B when the total wiring length is considered. However, with respect to the delay at the terminal v1, a difference described by the following formula (6) exists between the cases shown in FIGS. 1A and 1B.                                           Da            ⁢                          xe2x80x83                        ⁢                          (              v1              )                                -                      Db            ⁢                          xe2x80x83                        ⁢                          (              v1              )                                      =                                            {                                                r                  ⁢                                      xe2x80x83                                    ⁢                  d                  xc3x97                                      (                                          C                      +                      C1                      +                      C2                                        )                                                  +                                  R                  xc3x97                                      (                                                                  C                        /                        2                                            +                      C1                      +                      C2                                        )                                                              }                        -                          {                                                r                  ⁢                                      xe2x80x83                                    ⁢                  d                  xc3x97                                      (                                                                  3                        ⁢                                                  C                          /                          2                                                                    +                      C1                      +                      C2                                        )                                                  +                                  R                  xc3x97                  C1                                            }                                =                                    r              ⁢                              xe2x80x83                            ⁢              d              xc3x97                              (                                                      -                    C                                    /                  2                                )                                      +                          R              xc3x97              C2                                                          (        6        )            
As may be seen from the above formula (6), in a relationship Rxc3x97C2 greater than rdxc3x97(xe2x88x92C/2) stands, the wiring delay at the terminal v1 in the case shown in FIG. 1B is shorter than the wiring delay at the terminal v1 in the case shown in FIG. 1A.
Therefore, it is not necessarily the case that the wiring delay for a shortest total wiring length is always the shortest wiring delay. For this reason, there was a problem in that, according to the conventional method which determines the wiring so that the wiring length becomes the shortest, it is impossible to determine the wiring by accurately taking into consideration the delay of the actual wiring from one terminal to another terminal. In addition, even if the shortest wiring is determined according to the conventional method, a rerouting of the wiring is made depending on the wiring density or disorder which occurs thereafter, and there was another problem in that the wiring which is determined does not accurately take into account the delay of the actual wiring which is finally obtained.
Accordingly, it is a general object of the present invention to provide a novel and useful global routing determination method and storage medium, in which the problems described above are eliminated.
Another and more specific object of the present invention is to provide a global routing determination method which can determine a global routing of a circuit by accurately taking into account a delay of an actual wiring from one terminal to another terminal, and to provide a computer-readable storage medium which stores a program for causing a computer to determine the global routing of the circuit according to such a global routing determination method.
Still another object of the present invention is to provide a global routing determination method which successively divides a region which includes cells forming a circuit into a plurality of blocks, and hierarchically determines a global routing among the cells while arranging the cells in the blocks, comprising the steps of (a) selecting a K-pattern which indicates a position of at least one terminal which is to be coupled by a wiring with respect to a predetermined number of blocks, from a registered K-pattern group, (b) reading Q-patterns which indicate wiring patterns with respect to the selected K-pattern, from a registered Q-pattern group, and (c) determining, as a global routing, a Q-pattern which has a wiring from a source terminal to a target terminal within the selected K-pattern with a signal delay time satisfying a predetermined condition, from among the read Q-patterns, where the predetermined condition places priority on a total wiring length than a density or disorder of wirings among the blocks in which the source terminal and the target terminal exist. According to the global routing determination method of the present invention, it is possible to determine the global routing by accurately taking into consideration a delay of the actual wiring from one terminal to another terminal, thereby enabling design of a high-performance circuit.
A further object of the present invention is to provide a global routing determination method described above, wherein the step (c) determines, as the global routing, a Q-pattern which minimizes COST(Q) described by a formula
COST(Q)=COSTv1(Q)xc3x97xcex4(Q, V1)+COSTv2(Q)xc3x97xcex4(Q, V2)+COSTH1(Q)xc3x97xcex4(Q, H1)+COSTH2(Q)xc3x97xcex4(Q, H2)
where each read Q-pattern is made up of 2xc3x972 blocks, boundaries x between two mutually adjacent blocks of the read Q-pattern are respectively denoted by V1, V2, H1 and H2, a function xcex4(Q, x) has a value 1 when a wiring passes through the boundary x and has a value 0 when a wiring does not pass through the boundary x, C1 and C2 are constants, C(x) denotes a number of wirings passing through the boundary x, W(x) denotes a number of wirings which can pass through the boundary, and relationships
COSTV1(Q)=C1(C(v1)xe2x88x92W(V1))+C2
COSTV2(Q)=C1(C(v2)xe2x88x92W(V2))+C2
COSTH1(Q)=C1(C(H1)xe2x88x92W(H1))+C2
COSTH2(Q)=C1(C(H2)xe2x88x92W(H2))+C2
stand.
Another object of the present invention is to provide a global routing determination method which successively divides a region which includes cells forming a circuit into a plurality of blocks, and hierarchically determines a global routing among the cells while arranging the cells in the blocks, comprising the steps of (a) selecting a K-pattern which indicates a position of at least one terminal which is to be coupled by a wiring with respect to a predetermined number of blocks, from a registered K-pattern group, (b) reading Q-patterns which indicate wiring patterns with respect to the selected K-pattern, from a registered Q-pattern group, and (c) determining, as a global routing, a Q-pattern which has a wiring from a source terminal to a target terminal within the selected K-pattern with a signal delay time satisfying a predetermined condition, from among the read Q-patterns, where the step (c) determines, as the global routing, a Q-pattern which minimizes a slack S described by formulas   S  =                    ∑                  ∀          targeti                    ⁢      0        :                            maxDelay          ⁢                      xe2x80x83                    ⁢                      (            i            )                          -                  delay          ⁢                      xe2x80x83                    ⁢                      (            i            )                              ≧      0      xe2x80x83delay(i)xe2x88x92maxDelay(i):maxDelay(i)xe2x88x92delay(i) less than 0
where maxDelay (i) denotes a signal delay time caused by a wiring from a requested source terminal to a target terminal, and delay(i) denotes a signal delay time which is obtained as a result of actually forming the wiring from the source terminal to the target terminal. According to the global routing determination method of the present invention, it is possible to determine the global routing by accurately taking into consideration a delay of the actual wiring from one terminal to another terminal, thereby enabling design of a high-performance circuit.
Still another object of the present invention is to provide a global routing determination method described above, wherein the signal delay time delay(i) is an Elmore delay described by a formula       D    ⁢          xe2x80x83        ⁢          (      v      )        =            rdC      s0        +                  ∑                  ev          ∈                      path            ⁢                          xe2x80x83                        ⁢                          (                              s0                ,                v                            )                                          ⁢              xe2x80x83            ⁢                        r          ev                ⁢                  xe2x80x83                ⁢                  (                                                    C                ev                            /              2                        +            Cv                    )                    
where a tree T has a source s0, an edge from a node v towards the source s0 is denoted by ev, a resistance of the edge ev is denoted by rev, a capacitance of the edge ev is denoted by Cev, a subtree of the node v is denoted by Tv, a capacitance of the subtree Tv is denoted by Cv, an ON-resistance of an output driver of the source s0 is denoted by rd, a sum total of wiring lengths is denoted by Cs0 and the Elmore delay D(v) indicates a delay from the source s0 to the target v.
A further object of the present invention is to provide a computer-readable storage medium which stores a program for causing a computer to successively divide a region which includes cells forming a circuit into a plurality of blocks, and to hierarchically determine a global routing among the cells while arranging the cells in the blocks, comprising first means for causing the computer to select a K-pattern which indicates a position of at least one terminal which is to be coupled by a wiring with respect to a predetermined number of blocks, from a registered K-pattern group, second means for causing the computer to read Q-patterns which indicate wiring patterns with respect to the selected K-pattern, from a registered Q-pattern group, and third means for causing the computer to determine, as a global routing, a Q-pattern which has a wiring from a source terminal to a target terminal within the selected K-pattern with a signal delay time satisfying a predetermined condition, from among the read Q-patterns, where the predetermined condition places priority on a total wiring length than a density or disorder of wirings among the blocks in which the source terminal and the target terminal exist. According to the computer-readable storage medium of the present invention, it is possible to determine the global routing by accurately taking into consideration a delay of the actual wiring from one terminal to another terminal, thereby enabling design of a high-performance circuit.
Another object of the present invention is to provide a computer-readable storage medium which stores a program for causing a computer to successively divide a region which includes cells forming a circuit into a plurality of blocks, and to hierarchically determine a global routing among the cells while arranging the cells in the blocks, comprising first means for causing the computer to select a K-pattern which indicates a position of at least one terminal which is to be coupled by a wiring with respect to a predetermined number of blocks, from a registered K-pattern group, second means for causing the computer to read Q-patterns which indicate wiring patterns with respect to the selected K-pattern, from a registered Q-pattern group, and third means for causing the computer to determine, as a global routing, a Q-pattern which has a wiring from a source terminal to a target terminal within the selected K-pattern with a signal delay time satisfying a predetermined condition, from among the read Q-patterns, where the third means determines, as the global routing, a Q-pattern which minimizes a slack S described by formulas   S  =                    ∑                  ∀          targeti                    ⁢      0        :                            maxDelay          ⁢                      xe2x80x83                    ⁢                      (            i            )                          -                  delay          ⁢                      xe2x80x83                    ⁢                      (            i            )                              ≧      0      xe2x80x83delay(i)xe2x88x92maxDelay(i):maxDelay(i)xe2x88x92delay(i) less than 0
where maxDelay (i) denotes a signal delay time caused by a wiring from a requested source terminal to a target terminal, and delay(i) denotes a signal delay time which is obtained as a result of actually forming the wiring from the source terminal to the target terminal. According to the computer-readable storage medium of the present invention, it is possible to determine the global routing by accurately taking into consideration a delay of the actual wiring from one terminal to another terminal, thereby enabling design of a high-performance circuit.
Other objects and further features of the present invention will be apparent from the following detailed description when read in conjunction with the accompanying drawings.